package vip.george.p0011;

public class P11 {


    /**
     * 暴力法：穷举所有的情况，找到最大的面积
     * @param height
     * @return
     */
    public int maxArea(int[] height) {
        int maxArea = 0;
        for (int i = 0; i < height.length; i++) {
            for (int j = i + 1; j < height.length; j++) {
                int area = Math.min(height[i], height[j]) * (j - i);
                maxArea = Math.max(maxArea, area);
            }
        }
        return maxArea;
    }


    /**
     * 双指针法:
     * 贪心算法，每步最优策略
     * @param height
     * @return
     */
    public int maxArea2(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int maxArea = 0;
        while (left < right) {
            int currentArea = Math.min(height[left], height[right]) * (right - left);
            maxArea = Math.max(maxArea, currentArea);
            // 根据公式： [S = h * w]。宽度每次移动一个指针时都减1，要想S变大，则要使h变大,h又是由短柱子决定的
            //只需要移动相对短柱子的指针，因为短的柱子会决定最终的容量（相反的，如果移动长柱子的指针，则无论移动后新柱子有多高，都需要根据短柱子来确定高度，并且之间的距离变小了，则必会比未移动前的面积小）
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return maxArea;
    }

    public static void main(String[] args) {
        P11 p11 = new P11();
        System.out.println(p11.maxArea2(new int[]{1,8,6,2,5,4,8,3,7}));
        System.out.println(p11.maxArea2(new int[]{1,1}));
        System.out.println(p11.maxArea2(new int[]{4,3,2,1,4}));
        System.out.println(p11.maxArea2(new int[]{1,2,1}));
        System.out.println(p11.maxArea2(new int[]{8,7,2,1}));
    }


}
